package com.chenken;


/**
 *	最长公共子串	(LCS)
 *     	子串:连续的 
 *  状态转移方程:
 * 	 如果str1[i-1] = str2[j-1],dp(i,j) = dp[i-1,j-1] + 1	
 * 	 如果str1[i-1] != str2[j-1],dp(i,j) = 0	
 *      最长公共子串是dp(i,j)中的最大值
 */
public class LongestCommonSubString {
	
	public int lcs1(String text1, String text2) {
		if(text1 == null || text2 == null || "".equals(text1) || "".equals(text2)) {
			return 0;
		}
		char[] textArray1 = text1.toCharArray();
		char[] textArray2 = text2.toCharArray();
		int[][] table = new int[textArray1.length+1][textArray2.length+1];
		int max = 0;
		for(int row = 1;row < table.length;row++) {
			char char1 = textArray1[row-1];
			for(int col = 1;col < table[row].length;col++) {
				if(char1 == textArray2[col-1]) {
					table[row][col] = table[row-1][col-1] + 1;
					max = Math.max(max,table[row][col]);
				}
			}
		}
		return max;
    }
	
	public int lcs2(String text1, String text2) {
		if(text1 == null || text2 == null || "".equals(text1) || "".equals(text2)) {
			return 0;
		}
		char[] charArray1 = text1.toCharArray();
		char[] charArray2 = text2.toCharArray();
		char[] rowChars = charArray1,colsChars = charArray2;
		if(charArray1.length < charArray2.length) {
			colsChars = charArray1;//	列
			rowChars = charArray2;//	行
		}
		int[] dp = new int[colsChars.length+1];
		int max = 0;
		for(int row = 1;row <= rowChars.length;row++) {
			int cur = 0;
			for(int col = 1;col <= colsChars.length;col++) {
				int leftTop = cur;
				cur = dp[col];
				if(rowChars[row-1] != charArray2[col-1]) {
					dp[col] = 0;
				}else {
					dp[col] = leftTop + 1;
					max = Math.max(max,dp[col]);
				}
			}
		}
		return max;
    }
	
	public static void main(String[] args) {
		//String text1 = "abc", text2 = "def";
		String text1 = "abcde", text2 = "def";
		//String text1 = "abcdefg", text2 = "abcd";
		System.out.println(new LongestCommonSubString().lcs1(text1, text2));
		System.out.println(new LongestCommonSubString().lcs2(text1, text2));
	}
}
